package com.shuang.tree41;

public class LowestCommonAncestor {

    //利用搜索树的性质 当我们从上向下去递归遍历，第一次遇到 当前节点的数值是在[q, p]或者[p, q]区间中，那么cur就是 q和p的最近公共祖先
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        //终止条件 不要也可以 因为题目中说了p、q 为不同节点且均存在于给定的二叉搜索树中。也就是说一定会找到公共祖先的，所以并不存在遇到空的情况。
        if (root == null) {
            return null;
        }

        // 遍历二叉就搜索树的时候是寻找区间[p->val, q->val]（注意这里是左闭右闭）
        //并且只需要遍历一条边即可 不需要在中接收处理逻辑  找到了直接返回 (使用if语句判断)

        //往左遍历的情况 不清楚 pq 谁大所以都要判断一下 当前节点的值要大于p和q的值
        if (root.val > q.val && root.val > p.val) {
            TreeNode left = lowestCommonAncestor(root.left, p, q);
            if (left != null) {
                return left;
            }
        }

        //精简一下 往右遍历情况
        if (root.val < p.val && root.val < q.val) {

            return lowestCommonAncestor(root.right, p, q);
        }

        //剩下的其他情况 即 节点在区间（p->val <= cur->val && cur->val <= q->val）或者 （q->val <= cur->val && cur->val <= p->val）中，那么cur就是最近公共祖先了，直接返回cur。
        return root;
    }
}
